#ifndef __PERMUTATION_H__
#define __PERMUTATION_H__
#include <vector>
using namespace std;
/*
* leetcode 46 全排列
* 
* 例如: 求 {1, 2, 3} 的 全排列, 给出的集合没有重复元素
* 树形结构如下:
*				123(000)
*		1-23(100)		...
* 12-3(110)	 13-2(101)		...
* 123(111)		132(111)		...
* 
* 和组合问题不同, 全排列在每层中需要选取任意的元素; 而组合问题则是通过 startIndex 选取后面的元素
* 这里可以通过 bUsed 数组来记录元素是否被选取
*/
void BackTrackingPermutation(const vector<int>& set, vector<int>& path, vector<vector<int>>& results, vector<bool>& bUsed) {
	if (path.size() == set.size()) {
		results.push_back(path);
		return;
	}

	//每层对所有元素进行检索
	for (int i = 0; i < set.size(); i++) {
		if (bUsed[i])
			continue;
		
		//元素在该分支未被使用时加入
		path.push_back(set[i]);
		bUsed[i] = true;
		BackTrackingPermutation(set, path, results, bUsed);
		path.pop_back();
		bUsed[i] = false;
	}
}

/*
* leetcode 47 全排列 II
* 当集合中有重复元素, 需要考虑去重
* 
* 最终的思路跟 组合总和III 相同, 同样是 对集合进行排序 -> 树层去重
*/
void BackTrackingPermutationII(const vector<int>& set, vector<int>& path, vector<vector<int>>& results, vector<bool>& bUsed) {
	if (path.size() == set.size()) {
		results.push_back(path);
		return;
	}

	for (int i = 0; i < set.size(); i++) {
		if (bUsed[i] || (i > 0 && !bUsed[i - 1] && set[i] == set[i - 1]))
			continue;

		path.push_back(set[i]);
		bUsed[i] = true;
		BackTrackingPermutationII(set, path, results, bUsed);
		path.pop_back();
		bUsed[i] = false;
	}
}
#endif // !__PERMUTATION_H__

